Матч
194, Нечетные и четные (OddsAndEvens)
Дивизион 1,
Уровень 2
Целое число может быть нечетным и
четным. Рассмотрим операции сложения и умножения на четных и нечетных числах:
EVEN + EVEN = EVEN
EVEN + ODD = ODD
ODD + ODD = EVEN
EVEN * EVEN = EVEN
EVEN * ODD = EVEN
ODD * ODD = ODD
Выбран некоторый набор целых
чисел и вычислены все их попарные суммы и произведения. Все суммы занесены в
массив sums, а произведения – в products. Причем заносятся не суммы и
произведения чисел, а слова “ODD” и “EVEN” в зависимости от того, являются ли они
нечетным или четным числом.
В задаче необходимо вернуть
строку "EVEN <x> ODD <y>", где <x> – количество
четных чисел в наборе, а <y> – количество нечетных чисел.
Класс: OddsAndEvens
Метод: string
find(vector<string> sums, vector<string> products)
Ограничения: sums содержит n*(n-1)/2 элементов, где 0 £ n £ 100.
Вход. Массив попарных сумм sums и произведений products чисел.
Выход. Строка "EVEN <x> ODD <y>", где
<x> – количество четных чисел в наборе, а <y> – количество нечетных
чисел.
Пример входа
sums |
products |
{"EVEN"} |
{"ODD"} |
{"EVEN","ODD","ODD"} |
{"ODD","EVEN","EVEN"} |
{"ODD","EVEN","ODD","EVEN","ODD","EVEN"} |
{"ODD","EVEN","EVEN","EVEN","ODD","ODD"} |
Пример выхода
"EVEN 0 ODD 2"
"EVEN 1 ODD 2"
"EVEN 1 ODD 3"
РЕШЕНИЕ
математика
Подсчитаем в переменной OddSums
количество нечетных чисел в массиве сумм sums, а в переменной OddProducts
количество нечетных чисел в массиве произведений products. Поскольку sums
содержит n * (n – 1 ) / 2 элементов, то простым перебором находим количество
чисел в исходном наборе n.
Произведение чисел может быть
нечетным тогда и только тогда, когда оба числа нечетные. Поэтому если набор
чисел содержит i нечетных чисел, то количество
пар произведений, которые будут нечетными, равно i * (i – 1) / 2.
Остальные n – i чисел будут четными. Сумма будет нечетной, если одно из чисел
четно, а другое – нечетно. Но у нас имеется i
нечетных и n – i четных чисел, поэтому нечетных сумм будет i * (n – i). Перебираем все возможные значения i от 0 до n и если оба выше приведенные равенства имеют место, то возвращаем
результат. Иначе возвращаем "IMPOSSIBLE".
ПРОГРАММА
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class OddsAndEvens
{
public:
string find(vector<string> sums, vector<string> products)
{
char res[50];
int i, OddSums =
count(sums.begin(),sums.end(),"ODD");
int n, OddProducts =
count(products.begin(),products.end(),"ODD");
for(n = 0; n*(n-1)/2 != sums.size();
n++);
for(i = 0; i <= n; i++)
if (i*(i-1)/2 == OddProducts &&
i*(n-i) == OddSums)
{
sprintf(res, "EVEN %d ODD %d",
n - i, i);
return res;
}
return "IMPOSSIBLE";
}
};